package com.dy.查找.动态表查找.二叉排序树;

import com.dy.树与二叉树.二叉树.链式存储.BiTree;
import com.dy.树与二叉树.二叉树.链式存储.BiTreeNode;
import jdk.nashorn.internal.ir.BinaryNode;

/**
 * 左子树所有节点都小于根，右子树所有节点都大于根
 * 左右子树也都是二叉排序树
 *          20
 *        10    30
 *     5      29    90
 *   1   7        44
 *        8
 */
public class BinarySortTree {
    public static void main(String[] args) {
        BinarySortTree binarySortTree = new BinarySortTree();
        BiTreeNode root = new BiTreeNode(20);
        binarySortTree.inseartBST(10, root);
        binarySortTree.inseartBST(30, root);
        binarySortTree.inseartBST(5, root);
        binarySortTree.inseartBST(1, root);
        binarySortTree.inseartBST(7, root);
        binarySortTree.inseartBST(90, root);
        binarySortTree.inseartBST(44, root);
        binarySortTree.inseartBST(8, root);
        binarySortTree.inseartBST(29, root);
        BiTree roo = new BiTree(root);
        roo.levelTraverse(roo.root);
        removeBST(root, 5);
        roo = new BiTree(root);
        System.out.println();
        roo.levelTraverse(roo.root);
        //System.out.println(binarySortTree.searchBST(root, 44).data);
    }

    BiTreeNode searchBST(BiTreeNode tree, int k) {
        if ((int) tree.data == k) {
            return tree;
        } else {
            if ((int) tree.data > k) {
                return searchBST(tree.lchild, k);
            } else return searchBST(tree.rchild, k);
        }

    }

    public boolean inseartBST(int key, BiTreeNode root) {
        if ((int) root.data == key) {
            return false;
        }//不能插入相同的值
        if ((int) root.data > key) {
            if (root.lchild == null) {
                BiTreeNode newNode = new BiTreeNode(key);
                root.lchild = newNode;
                return true;
            } else {
                return inseartBST(key, root.lchild);
            }
        } else {
            if (root.rchild == null) {
                BiTreeNode newNode = new BiTreeNode(key);
                root.rchild = newNode;
                return true;
            } else {
                return inseartBST(key, root.rchild);
            }
        }
    }

    /**
     * 被删除节点是树叶节点(没有子树):最简单,直接删除,将该节点置为null即可
     * 　　　　被删除节点有一个子节点(左子树或右子树):是该节点的父节点指向该节点的子节点(左或右).见图1
     * 　　　　被删除节点有两个子节点:用其右子树中的最小值代替该节点上的值,删除其右子树上的最小值. 即找到该节点中序遍历后的下一个值换过来
     */
    private static void removeBST(BiTreeNode root, int key) {
        if (root.data == null) return;
        //找到要删除的节点
        BiTreeNode parentNode = root;
        BiTreeNode removeNode = root;
        boolean isLeftChild = true;
        //找到被删除的节点和其父节点
        while (removeNode != null && (int) removeNode.data != key) {
            parentNode = removeNode;
            int tmp = (int) removeNode.data;
            if (tmp > key) {

                removeNode = removeNode.lchild;
                isLeftChild = true;
            } else {
                removeNode = removeNode.rchild;
                isLeftChild = false;
            }
        }

        //如果删除的是叶子节点，则直接删除
        if (removeNode.rchild == null && removeNode.lchild == null) {
            if (isLeftChild) {
                parentNode.lchild = null;
            } else parentNode.rchild = null;
        }
        //如果被删除节点左孩子是null，则把被删除节点的右孩子赋给根
        else if (removeNode.lchild == null) {
            if (isLeftChild) {
                parentNode.lchild = removeNode.rchild;
            } else parentNode.rchild = removeNode.rchild;
        }
        //如果被删除节点右孩子是null，则把被删除节点的左孩子赋给根
        else if (removeNode.rchild == null) {
            if (isLeftChild) {
                parentNode.lchild = removeNode.lchild;
            } else parentNode.rchild = removeNode.lchild;
        }
        //被删除节点左右孩子都不是null，找右孩子的最左孩子用于替换
        else {
            BiTreeNode innext = removeNode.rchild;
            //如果innext的左孩子为null，则把 innext的值赋给removeNode，并让removeNode的右孩子等于innext的右孩子
            if (innext.lchild == null) {
                removeNode.data = innext.data;
                removeNode.rchild = innext.rchild;
            }
            //否则找最左儿子
            else {
                BiTreeNode innextParent = removeNode;
                while (innext.lchild != null) {
                    innextParent = innext;
                    innext = innext.lchild;
                }
                removeNode.data = innext.data;
                innextParent.lchild = innext.rchild;

            }
        }
    }

}
